/*******************************************************************************
* FileName:         Haffman.cpp
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/11/20 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #9
*******************************************************************************/

#include "Huffman.h"
#include <queue>
#include <algorithm>

using namespace std;

HuffmanTree::HuffmanTree(const int* Table) : root(nullptr) {
    // 小根堆优先队列
    auto cmp = [](node* a, node* b) { return a->fre > b->fre; };
    priority_queue<node*, vector<node*>, decltype(cmp)> pq(cmp);

    // 构造初始叶子节点并插入优先队列
    for (int i = 0; i < 26; i++) {
        if (Table[i] > 0) {
            pq.push(new node('a' + i, Table[i]));
        }
    }

    // 构造哈夫曼树
    while (pq.size() > 1) {
        node* left = pq.top(); pq.pop();
        node* right = pq.top(); pq.pop();

        node* parent = new node(0, left->fre + right->fre);  //使用小根堆特性构造双亲节点
        parent->leftchild = left;
        parent->rightchild = right;
        pq.push(parent);
    }

    // 设置根节点
    if (!pq.empty()) {
        root = pq.top();
        buildCodeTable(root, "");  //使用buildCodeTable递归构造
    }
}

void HuffmanTree::buildCodeTable(node* Node, const string& code) {
    if (!Node) return;
    if (!Node->leftchild && !Node->rightchild) { // 叶子节点
        codeTable[Node->ch] = code;
        return;
    }
    buildCodeTable(Node->leftchild, code + '0');  //递归插入左节点
    buildCodeTable(Node->rightchild, code + '1');  //递归插入右节点
}

HuffmanTree::~HuffmanTree() {
    deleteroot(root);  //使用递归函数析构
}

void HuffmanTree::deleteroot(node* Node) {
    if (!Node) return;
    deleteroot(Node->leftchild); //递归释放左节点
    deleteroot(Node->rightchild); //递归释放右节点
    delete Node;
}

string HuffmanTree::Encode(string message) {
    string res;
    for (char ch : message) {
        if (codeTable.find(ch) == codeTable.end()) {
            throw runtime_error("Character not in frequency table: " + string(1, ch)); //未找到对应字符
        }
        res += codeTable[ch]; //插入节点编码
    }
    return res;
}

string HuffmanTree::Decode(string message) {
    string res;
    node* cur = root;  //设置翻译节点
    for (char ch : message) {
        if (ch == '0')
            cur = cur->leftchild;
        else if (ch == '1')
            cur = cur->rightchild;
        else
            throw runtime_error("Invalid Huffman code character: " + string(1, ch));  //无效字符

        if (!cur->leftchild && !cur->rightchild) { // 到达叶子节点
            res += cur->ch;
            cur = root; // 回到根节点
        }
    }
    return res;
}